
# 使用深度优先遍历求图(使用稀疏图)的连通分量  
class Component:
    def __init__(self, graph):
        self.graph = graph
        self.visited = [False for _ in range(self.graph.V())]
        self._count = 0
    
    # 返回联通分量的个数
    def components(self):
        for i in range(self.graph.V()):
            if not self.visited[i]:
                self.dfs(i)
                self._count += 1
        return self._count

    def dfs(self, v):
        self.visited[v] = True
        # 这里局限于使用连接表表示的图
        for u in self.graph.edges(v):  # 遍历所有邻边
            if not self.visited[u]:
                self.dfs(u)

if __name__ == '__main__':
    from graph import build_graph

    # components.txt对应的图为: 示例2.png
    graph = build_graph('components.txt', 13)
    component = Component(graph)
    print("连通分量的个数: ", component.components())